#define _CRT_SECURE_NO_WARNINGS 1

class Solution
{
public:
    bool check[16];
    int ret;
    int countArrangement(int n)
    {
        dfs(1, n);
        return ret;
    }

    void dfs(int pos, int n)
    {
        if (pos == n + 1)
        {
            ret++;
            return;
        }

        for (int i = 1; i <= n; i++)
        {
            if (!check[i] && (pos % i == 0 || i % pos == 0))
            {
                check[i] = true;
                dfs(pos + 1, n);
                check[i] = false;
            }
        }

    }
};